import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

/**
 *  * 这是 LeetCode 第 26 题 "删除有序数组中的重复项" 的解决方案
 *  https://leetcode.cn/problems/remove-duplicates-from-sorted-array
 */
class RemoveDuplicatesFromSortedArray{
    /**
     * 方法：
     * removeDuplicates
     *
     * 功能：
     * 移除排序数组中的重复元素，并返回新数组的长度。
     *
     * 实现逻辑：
     * 1. 获取数组长度 `len`，如果数组为空直接返回0。
     * 2. 定义两个指针 `i` 和 `j`，均初始化为1。`i` 用于记录不重复元素的位置，`j` 用于遍历数组。
     * 3. 使用 `while` 循环遍历数组，直到 `j` 达到数组末尾。
     * 4. 如果当前元素 `nums[j]` 与前一个不同元素 `nums[i-1]` 不相等，则将 `nums[j]` 赋值给 `nums[i]`，并将 `i` 向后移动一位。
     * 5. 无论是否发现新的唯一元素，`j` 都向后移动一位继续检查下一个元素。
     * 6. 最终返回 `i`，即为去重后的有效数组长度。
     *
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(1)，只使用了常数级别的额外空间
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
         int len = nums.length;
         if(len == 0){
             return 0;
         }
         int i = 1, j = 1;
         while(j < len){
             if(nums[j] != nums[i-1]){
                 nums[i] = nums[j];
                 i++;
             }
             j++;
         }
         return i;
    }

    public void testRemoveDuplicates() {
        RemoveDuplicatesFromSortedArray solution = new RemoveDuplicatesFromSortedArray();

        // 测试用例1：常规数组，包含重复元素
        int[] nums1 = {1, 1, 2, 2, 3, 4, 4, 5};
        int result1 = solution.removeDuplicates(nums1);
        assertEquals(5, result1);
        assertArrayEquals(new int[]{1, 2, 3, 4, 5, 4, 4, 5}, nums1);

        // 测试用例2：全部元素都相同
        int[] nums2 = {1, 1, 1, 1, 1};
        int result2 = solution.removeDuplicates(nums2);
        assertEquals(1, result2);
        assertArrayEquals(new int[]{1, 1, 1, 1, 1}, nums2);

        // 测试用例3：没有重复元素
        int[] nums3 = {1, 2, 3, 4, 5};
        int result3 = solution.removeDuplicates(nums3);
        assertEquals(5, result3);
        assertArrayEquals(new int[]{1, 2, 3, 4, 5}, nums3);

        // 测试用例4：空数组
        int[] nums4 = {};
        int result4 = solution.removeDuplicates(nums4);
        assertEquals(0, result4);
        assertArrayEquals(new int[]{}, nums4);

        // 测试用例5：只有两个元素的数组
        int[] nums5 = {1, 1};
        int result5 = solution.removeDuplicates(nums5);
        assertEquals(1, result5);
        assertArrayEquals(new int[]{1, 1}, nums5);
    }

    public static void main(String[] args) {
        new RemoveDuplicatesFromSortedArray().testRemoveDuplicates();
        System.out.println("所有测试用例通过!");
    }
}